A trajectory pattern of a route refers to data describing the shape and/or direction of the route. For example, the trajectory pattern can include the segments through which the route passes and the directions of the segments. The trajectory pattern has a variety of purposes. For example, it can match a location of a vehicle or a user sensed using a technology such as Global Positioning System (GPS) to a corresponding location on the route. Generally, the trajectory pattern is crucial to many applications such as vehicle tracking, fleet management, and the like.
It is rather time-consuming and laborious to obtain a trajectory pattern manually. Besides, a manually collected trajectory pattern hardly satisfies the practical demands on accuracy. For bus lines in a city, there could be thousands of routes, while each route likely further includes tens or even hundreds of road segments. Further, due to various reasons such as municipal construction, road planning, traffic management and the like, the road segments in one route could vary with time. For example, statistics shows that there would be 7%-13% of the routes changing in average each month, which will cause corresponding updates of a considerable percentage of trajectory patterns.
It has been proposed to generate a road network using various methods, such as a grid-based method. Afterwards, the original GPS data collected by the vehicle can be mapped to the road network, so as to infer a trajectory pattern using Welch test. However, the process per se of generating a road network has a high computational complexity and a time cost. In many cases such as location data missing for some segments, low location data precision, and complex segments existing in the route result in generation of the road network to be error-prone. Additionally, the precision of the road network likely exceeds the precision requirement on the trajectory pattern in applications such as fleet management, which causes wastes of computational resources.